Algorithmes gloutons

On appelle système de monnaie la donnée d'une liste strictement croissante d'entiers représentant l'ensemble des valeurs des différentes pièces et billets d'une monnaie. Le système de l'euro est représenté par la liste l = [1, 2, 5, 10, 20, 50, 100, 200, 500].

Étant donné une somme $s\in\N$ à payer et un système de monnaie, le problème du rendu de monnaie consiste à déterminer comment réaliser la somme $s$ avec les valeurs existantes, en minimisant le nombre de pièces/billets utilisés. On supposera que la liste l contient la valeur $1$, ce qui assure que toute somme peut être réalisée.

La stratégie gloutonne consiste à choisir à chaque étape la plus grande valeur qui reste inférieure à la somme restante.

1. Appliquer la stratégie gloutonne pour rendre $154$€ avec le système de l'euro.
2. Écrire une fonction plus_grande_valeur qui prend en argument un entier $r\in\N^*$, représentant la somme restante à payer et une liste l représentant un système de monnaie, et renvoie la plus grande valeur du système qui soit $\leq r$.
3. Écrire une fonction rendu qui prend en argument une somme $s$ et une liste l représentant un système de monnaie, et renvoie une liste contenant les valeurs utilisées pour payer la somme $s$, en utilisant la stratégie gloutonne.

4. Donner un exemple de système de monnaie et d'une somme $s$, pour lesquels la stratégie gloutonne ne renvoie pas une solution optimale.

   Un système de monnaie est dit canonique si la méthode gloutonne renvoie toujours une solution optimale. Le système de l'euro est canonique.

On s'intéresse à un problème de réservation d'une salle, sur une période de plusieurs jours, à partir d'un premier jour.

Chaque demande de réservation est représentée par un couple d'entiers (a, b), où a représente le jour de début de la réservation, et b le jour de fin (inclus). En particulier $a\leq b$ et $a\geq 1$.

On considère une liste l contenant les demandes de réservation. l est une liste de couples, par exemple l = [(1,5), (5,6), (2,3)]. On peut accéder aux jours de début et de fin d'une demande de réservation par l'instruction (deb, fin) = l[i].

Les réservations ne sont pas toutes compatibles entre elles et on souhaite choisir un planning de réservations qui maximise le nombre de réservations. Pour l'exemple précédent, un planning de réservation optimal est donc [(2,3), (5,6)].

La stratégie gloutonne consiste à choisir les réservations par ordre chronologique. À chaque étape on choisit la réservation compatible avec les précédentes qui s'arrête le plus tôt.

1. Écrire une fonction est_liste_reserv qui prend en argument une liste de couples d'entiers et renvoie True si cette liste représente bien des demandes de réservations, et False sinon.

2. Écrire une fonction qui prend en argument la liste l et un entier d représentant un jour, et renvoie la demande de réservation qui termine le plus tôt, parmi les réservations qui commencent après (strictement) le jour d. S'il n'y a pas de telle réservation, on renverra la valeur spéciale None.

   On pourra éventuellement initialiser une variable à une valeur None.

3. Implémenter une fonction reservation_gloutonne qui prend en argument la liste l et renvoie une nouvelle liste contenant les réservations choisies par la méthode gloutonne.

4. La complexité de l'implémentation précédente est quadratique. Proposer une implémentation d'une complexité $O(n\ln n)$.

   On pourra utiliser les instructions ll = [(y,x) for x,y in l] et ll.sort(), pour trier ll selon l'ordre lexicographique.

5. Justifier que le planning de réservations choisi par la stratégie gloutonne est une réservation optimale.

   On pourra commencer par justifier qu'il existe une réservation optimale dont la première réservation est la réservation qui termine le plus tôt.

On représente des parties de $\db{0,n-1}$ par des listes de taille $n$ de booléens. On dit qu'une famille $\mc F$ de parties de $\db{0,n-1}$ recouvre $\db{0,n-1}$ si $\bigcup\limits_{A\in\mc F} A = \db{0,n-1}$. L'objectif est d'extraire d'une telle famille une sous-famille couvrante avec le moins de parties possible.

1. Écrire une fonction sous_couverture_min qui prend en argument une famille couvrante de $\db{0,n-1}$, représentée par une liste de parties, et renvoie une sous-famille couvrante construite de manière gloutonne, en cherchant à minimiser le nombre de parties.
2. Expliciter la complexité de votre implémentation, en fonction de $n$, de $m = |\mc F|$, et/ou de $M = \sum\limits_{A\in\mc F} |A|$.
3. Montrer à travers un exemple que l'algorithme glouton précédent n'est pas optimal.

4. Application : Un ensemble de villes est représenté par un graphe non orienté. On veut installer un nombre minimal d'antennes cellulaires pour couvrir le réseau téléphonique. Chaque antenne est installée dans une ville, et couvre la ville, ainsi que ses villes voisines dans le graphe.

   Écrire une fonction qui prend en argument un graphe non orienté $\mc G$, et renvoie une répartition possible des antennes.

5. ★ On suppose qu'il existe une couverture optimale avec $m_o$ ensembles. On note $m_g$ le cardinal d'une couverture renvoyée par l'algorithme glouton, et on veut majorer $m_g$.
   1. On note $r_i$ le nombre d'éléments restants (non couverts) après $i$-étapes de l'algorithme glouton. Montrer que $$r_i\leq n\left(1 - \frac{1}{m_o}\right)^i.$$
   2. En déduire que $m_g \leq m_o \ln n$.
6. ★ Comment améliorer la complexité de votre implémentation ? Une solution optimale est en $O(M)$.

Lors d'une exploration extraterestrielle, $n$ points d'intérêts numérotés de $0$ à $n-1$ ont été déterminés. Un robot doit choisir un chemin à partir de son point initial qui lui permet de passer par tous les points d'intérêts une et une seule fois. L'objectif est de trouver un chemin de longueur totale minimale. Le robot n'a pas besoin de revenir à son point initial à la fin.

Un tel chemin est représenté par une liste de longueur $n$ contenant les points d'intérêts dans leur ordre de visite.

On représente les distances entre chaque paire de points d'intérêt dans une liste de listes globale DISTANCE, que l'on pourra librement utiliser : pour $i,j\in\db{0,n-1}$, l'instruction DISTANCE[i][j] renverra la distance entre les points d'intérêts $i$ et $j$.

Par ailleurs, le point initial du robot est représenté par l'indice $n$ et les distances des points d'intérêts au point initial peuvent être récupérées par des appels DISTANCE[i][n] ou DISTANCE[n][i].